package com.dataStructures.search;

/**
 * 插值查找
 */
public class InsertValSearch {

	/**
	 * 查找次数
	 */
	public static int count = 0;

	public static void main(String[] args) {
		/*int[] arr = new int[100];
		for (int i = 0; i < 100; i++) {
			arr[i] = i + 1;
		}*/
		int[] arr = {1, 3, 5, 7, 9, 11, 19};
		int index = insertValSearch(arr, 0, arr.length - 1, 19);
		System.out.println(index);
		System.out.println("查找的次数：" + count);

	}

	public static int insertValSearch(int[] arr, int left, int right, int findVal) {
		count++;
		if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
			return -1;
		}
		int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
		int midVal = arr[mid];
		if (findVal > midVal) {
			return insertValSearch(arr, mid + 1, right, findVal);
		} else if (findVal < midVal) {
			return insertValSearch(arr, left, mid - 1, findVal);
		} else {
			return mid;
		}
	}
}
